#define _CRT_SECURE_NO_WARNINGS 1
const int N = 1e5 + 10;
int e[N * 2], ne[N * 2], h[N], idx;
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int se;
long long ans = 0;

class Solution {
public:
    long long dfs(int u, int f) {
        long long s = 1;
        for (int i = h[u]; i != -1; i = ne[i]) {
            int j = e[i];
            if (j == f)continue;
            s += dfs(j, u);
        }
        if (u)ans += (s + se - 1) / se;
        return s;
    }
    long long minimumFuelCost(vector<vector<int>>& roads, int seats) {
        memset(h, -1, sizeof h);
        memset(e, 0, sizeof e);
        ans = 0;
        idx = 0;
        memset(ne, 0, sizeof ne);
        for (auto it : roads) {
            int a = it[0];
            int b = it[1];
            add(a, b);
            add(b, a);
        }
        se = seats;
        //long long ans=0;
        dfs(0, -1);

        return ans;
    }

};